Image data includes a huge amount of information. It is therefore impractical to process image data as it is from the viewpoint of the memory capacity and communication speed. Techniques for compressing image data are therefore important.
One of international standards for image data compression is the JPEG (Joint Photographic Expert Group). JPEG adopts the DCT (discrete cosine transformation) method which involves irreversible encoding and the reversible encoding method which involves DPCM (differential pulse code modulation) in a two-dimensional space. The compression of image data according to the DCT method will now be described.
FIG. 18 is a block diagram showing a basic configuration of a system for performing image data compression and image data decompression according to the DCT method.
At the encoding end, a DCT process portion 100 performs a discrete cosine transformation (hereinafter referred to as “DCT”) process on original image data input thereto to output DCT coefficients. A quantizing portion 200 quantizes the DCT coefficients output by the DCT process portion 100 with reference to a quantization table 400 to output quantized DCT coefficients. Image quality and the amount of encoded information are controlled through such quantization. A Huffman encoding portion 206 performs a Huffman encoding process on the DCT coefficients output by the quantizing portion 200 to output compressed image data.
At the decoding end, a Huffman decoding portion 211 performs a Huffman decoding process on compressed image data with reference to an encoding table 500 to output quantized DCT coefficients. A dequantizing portion 700 performs dequantization on the quantized DCT coefficients with reference to the quantization table 400 to output DCT coefficients. A reverse DCT process portion 800 performs a reverse DCT process on the DCT coefficients to output reproduced image data.
Next, the DCT process performed by the DCT process portion 100 will be described. First, as shown in FIG. 19, image data is divided into a plurality of 8×8 pixel blocks. As shown in FIG. 20, one 8×8 pixel block includes 64 items of pixel data PXY (X, Y=0, . . . , 7). Two-dimensional DCT expressed by Equation 1 is performed on each of 8×8 pixel blocks thus divided.
(Equation 1)       S    UV    =            1      4        ⁢          C      U        ⁢          C      V        ⁢                  ∑                  X          =          0                7            ⁢                          ⁢                        ∑                      Y            =            0                    7                ⁢                                  ⁢                              (                                          P                XY                            -                              L                S                                      )                    ⁢          cos          ⁢                                                    (                                                      2                    ⁢                    X                                    +                  1                                )                            ⁢              U              ⁢                                                          ⁢              π                        16                    ⁢          cos          ⁢                                                    (                                                      2                    ⁢                    Y                                    +                  1                                )                            ⁢              V              ⁢                                                          ⁢              π                        16                                              where SUV (U, V=0, . . . , 7) represents DCT coefficients. When the bit precision of pixel data PXY is 12 bits, LS=128 and, when the bit precision of pixel data PXY is 12 bits, LS=2048.where SUV (U, V=0, . . . , 7) represents DCT coefficients. When the bit precision of pixel data PXY is 8 bits, LS=128 and, when the bit precision of pixel data PXY is 12 bits, LS=2048.        
As a result of the DCT process, 64 DCT coefficients SUV are obtained. The DCT coefficient S00 is referred to as “DC coefficient”, and the remaining 63 DCT coefficients are referred to as “AC coefficients”. As shown in FIG. 20, the number of horizontal frequency components at high frequencies included in a block which has been subjected to the DCT process increases from left to right, and the number of vertical frequency components at high frequencies included increased from top to bottom.
At the reverse DCT process portion 800, 64 pixel data PXY (X, Y=0, . . . , 7) are obtained from the DCT coefficients SUV through a reverse DCT process expressed by Equation 2.
(Equation 2)       P    XY    =                    1        4            ⁢                        ∑                      U            =            0                    7                ⁢                                  ⁢                              ∑                          V              =              0                        7                    ⁢                                    C              U                        ⁢                          C              V                        ⁢                          S              UV                        ⁢            cos            ⁢                                                            (                                                            2                      ⁢                      X                                        +                    1                                    )                                ⁢                U                ⁢                                                                  ⁢                π                            16                        ⁢            cos            ⁢                                                            (                                                            2                      ⁢                      Y                                        +                    1                                    )                                ⁢                V                ⁢                                                                  ⁢                π                            16                                            +          L      S      
As shown in FIG. 21, two-dimensional DCT is performed by two one-dimensional DCT circuits 110 and 130 and an inversion memory 120. The horizontal direction of an 8×8 pixel block is referred to “row direction”, and the vertical direction is referred to as “column direction”.
The one-dimensional DCT 110 performs one-dimensional DCT as expressed by Equation 3 on image data fx, and writes one-dimensional DCT coefficients FU representing the results in each row of the inversion memory 120.
(Equation 3)       F    U    =            1      4        ⁢          C      U        ⁢                  ∑                  X          =          0                7            ⁢              fx        ⁢                                  ⁢        cos        ⁢                                            (                                                2                  ⁢                  X                                +                1                            )                        ⁢            U            ⁢                                                  ⁢            π                    16                    
The one-dimensional DCT circuit 130 performs one-dimensional DCT on the one-dimensional DCT coefficients FU stored in each row of the inversion memory 120 and outputs the results as DCT coefficients SUV.
One-dimensional reverse DCT is expressed by Equation 4.
(Equation 4)   fx  =            ∑              U        =        0            7        ⁢                  C        U            ⁢              F        U            ⁢      cos      ⁢                                    (                                          2                ⁢                X                            +              1                        )                    ⁢          U          ⁢                                          ⁢          π                16            
A description will now be made on the Huffman encoding process performed by the Huffman encoding portion 206. FIG. 22 shows examples of DCT coefficients output by the quantizing portion 200. In FIG. 22, “A”, “B”, “C”, “D”, “E” and “F” represent values other than “0”.
The Huffman encoding portion 206 in FIG. 18 performs a Huffman encoding process on DCT coefficients output by the quantizing portion 200 to output compressed image data. Referring to encoding of a DC coefficient, the difference between the DC coefficient of the current block and the DC coefficient of the preceding block is obtained, and a Huffman code is assigned to the difference.
Referring to encoding of AC coefficients, as shown in FIG. 23, the AC coefficients are first arranged on a one-dimensional basis as a result of zigzag scan. The one-dimensionally arranged AC coefficients are encoded using run lengths representing the length of consecutive coefficients “0” (invalid coefficients) and the values of coefficients (valid coefficients) other than “0”. The valid coefficients are divided into groups, and a group number is assigned to each valid coefficient. When AC coefficients are encoded, a Huffman code is assigned to a combination of a run length and a group number. Original image data are encoded into compressed image data as described above.
[First Object]
As described above, a block consisting of 8×8=64 data is treated as one unit to be processed according to the JPEG method. At the DCT process, two-dimensional DCT is performed by performing one-dimensional DCT in the column direction and one-dimensional DCT in the row direction on data in each block. Similarly, at the reverse DCT process, two-dimensional reverse DCT is performed by performing one-dimensional reverse DCT in the column direction and one-dimensional reverse DCT in the row direction on data in each block. An inversion memory for storing 64 items of data in one block is used in such a DCT process and reverse DCT process.
In this case, as shown in FIG. 24(a), data are written in an inversion memory TM in the order of raster scan in the row direction and, as shown in FIG. 24(b), the data stored in the inversion memory TM are read in the order of raster scan in the column direction. As a result, data in each block can be rearranged from the order of raster scan in the row direction to the order of raster scan in the column direction.
In the Huffman encoding process and Huffman decoding process, a bank memory for storing 64 items of data of one block is used. At the encoding end, as shown in FIG. 25(a), data are written in a bank memory BM in the order of raster scan and, as shown in FIG. 25(b), the data stored in the bank memory BM are read in the order of zigzag scan. As a result, data in each block can be rearranged from the order of raster scan to the order of zigzag scan. At the decoding end, as shown in FIG. 25(b), data are written in a bank memory BM in the order of zigzag scan and, as shown in FIG. 25(a), the data stored in the bank memory BM are read in the order of raster scan. As a result, data in each block can be rearranged from the order of zigzag scan to the order of raster scan.
In order to increase the speed of a process, a plurality of items of data must be processed simultaneously. For example, at the DCT process and reverse DCT process, two inversion memories each having a storage capacity of 64 are used; and the same 64 items of data are stored in each of the two inversion memories; and different data are read from the two inversion memories simultaneously. This makes it possible to increase the data processing speed. Similarly, at the Huffman encoding process and Huffman decoding process, two bank memories each having a storage capacity of 64 are used; and the same 64 items of data are stored in each of the two bank memories; and different data are read from the two bank memories simultaneously. This makes it possible to increase the data processing speed.
However, two inversion memories are required for each of the DCT process and reverse DCT process, and two bank memories are required for each of the Huffman encoding process and Huffman decoding process. This hinders efforts toward reductions of the size and cost of a system.
It is therefore a first object to provide a data processor which is capable of rearranging data at a first speed and whose size and cost can be reduced.
[Second Object]
A block consisting of 8×8=64 data is treated as one unit to be processed according to the JPEG method. For example, at the encoding end, as shown in FIG. 26, quantized DCT coefficients output by the quantizing portion 200 (see FIG. 18) are stored in a bank memory 221 as data. As shown in FIG. 27, the data stored in the bank memory 221 are read in the order of zigzag scan in synchronism with a clock signal CLK and are sequentially transferred to a Huffman encoding circuit 222 through 11-bit data bus DB0.
In the example in FIG. 27, eight items of data “D0”, “D1”, “0”, “D2”, “0”, “0”, “D3” and “D4” are sequentially transferred. Here, “0” represents an invalid coefficient, and “D0”, “D1”, “D2”, “D3” and “D4” represent valid coefficients.
When AC coefficients are encoded, the Huffman encoding circuit 222 detects run lengths indicating the number of consecutive “0s” and valid coefficients based on the data sequentially transferred by the bank memory 221 and performs Huffman encoding based on combinations of a run length and a valid coefficient.
In the conventional Huffman encoding portion 206, items of data are transferred from the bank memory 221 to the Huffman encoding circuit 222 one by one as described above and, therefore, the number of cycles required for processing the data can not be reduced. In the above-described example, the time required for processing eight items of data corresponds to eight cycles of the clock signal CLK. Therefore, the speed of the process at the Huffman encoding portion 206 can not be increased. Similarly, the speed of the process at the Huffman decoding portion 211 can not be increased.
It is therefore a second object to provide a Huffman encoder with an improved processing speed. It is another object to provide a Huffman decoder with an improved processing speed.
[Third Object]
FIG. 28 is a block diagram showing an example of a conventional Huffman decoder. A head search process portion 311 detects the position of the head of a Huffman code from compressed image data and supplies compressed image data in a bit quantity corresponding to a maximum code length of Huffman codes counted from the detected head position to an address input terminal AD of a memory 312 as an address signal.
The memory 312 has a storage capacity of 2k words. Here, k represents the maximum code length of Huffman codes. In each address in the memory 312, decoded data associated with a Huffman code represented by the address are stored. Each decoded data consists of a run length and a group number as described above.
For example, if it is assumed that the maximum length k of Huffman codes is 16, decoded data corresponding to a 16-bit long Huffman code “1111111111110101” are stored in an address “111111111111010”. Decoded data corresponding to a 15-bit long Huffman code “111111111000010” are stored in two addresses “11111111100000X”. Here, X represents 0 and 1. Decoded data corresponding to a 2-bit long Huffman code “01” are stored in 214 addresses “01xxxxxxxxxxxxxx”.
Since 16-bit compressed image data corresponding to the maximum code length are thus supplied to the memory 312 as address signals, decoded data associated with a Huffman code shorter than the maximum code length must be stored in a plurality of addresses.
For example, when compressed image data include a 2-bit Huffman code “01”, 16-bit compressed image data “01 . . . ” are supplied to the memory 312 as an address signal. As a result, decoded data stored in an address “01 . . . ” are read and output from a data output terminal D0. Thus, the Huffman code included in the compressed image data is decoded.
As described above, since compressed image data in a bit quantity corresponding to the maximum code length k of Huffman codes are supplied to the memory 312 as an address signal in the conventional Huffman decoder, the memory 312 must have a storage capacity of 2k words.
In this case, decoded data associated with a Huffman code shorter than the maximum code length k are stored in a plurality of addresses. That is, extra decoded data must be stored in addresses in a quantity much greater than the number of Huffman codes. If it is assumed that the number of Huffman codes is represented by N, the utilization rate of the memory 312 is as very low as N/2k.
As a result, the circuit of the Huffman decoder becomes large-scale, and it becomes difficult to increase the processing speed.
It is therefore a third object to provide a Huffman decoder with a reduced size and an increased speed.